package fun.ticsmyc.dataStructure;

import fun.ticsmyc.tools.ArrayTools;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-08-18 21:37
 */
public class 堆 {

    private int size;
    private int[] arr;

    public 堆(int length){
        size = 0;
        arr =new int[length];
    }

    public void insert(int val){
        if(size < arr.length){
            int pos = size++;
            arr[pos] = val;
            while(arr[(pos-1)/2]  > arr[pos]){
                ArrayTools.swap(arr,pos,(pos-1)/2);
                pos = (pos-1)/2;
            }
        }
    }

    public int heapify(){
        if(size >0){
            ArrayTools.swap(arr,0,--size);
            int pos =0;
            while(2 *pos +1 <size){
                //有左孩子
                int smallest = 2*pos+2 <size && arr[2*pos+2]<arr[2*pos+1]  ? 2*pos+2 : 2*pos+1;
                if(arr[smallest] <arr[pos]){
                    ArrayTools.swap(arr,smallest,pos);
                    pos = smallest;
                }else{
                    break;
                }
            }
            return arr[size];
        }
        return -1;
    }
    public void print(){
        ArrayTools.printArray(arr);
    }

    public static void main(String[] args) {
        堆 heap = new 堆(9);
        int[] arr = new int []{9,8,7,6,5,4,3,2,1};
        for(int i=0;i<arr.length; ++i){
            heap.insert(arr[i]);
            heap.print();
        }
    }
}
